/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: dings
 * Date: 2024-07-11
 * Time: 17:58
 */
class MinStack {
    Stack<Integer> dataStack;//存储所有数据
    Stack<Integer> minStack;// 栈顶存储最小值数据 每次添加新数据时，和minStack栈顶元素比较，若<= ，则push进minStack

    public MinStack() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        dataStack.push(val);
        if (minStack.isEmpty()) {
            // 当minStack为空时，直接push进minStack
            minStack.push(val);
        } else {// 一定要有else 否则，minStack空时，同一个元素会在minStack中push两次
            if (val <= minStack.peek()) {
                // 一定要 <= ，因为dataStack中可能有多个相同的最小值，保证pop一次，minStack依然存储着最小值
                minStack.push(val);
            }
        }
    }

    public void pop() {
        // 操作总是在 非空栈 上调用
        int val = dataStack.pop();
        // 当dataStack栈顶元素为最小值时，也要弹出minStack的栈顶元素
        if (val == minStack.peek()) {
            minStack.pop();
        }
    }

    public int top() {
        return dataStack.peek();
    }

    public int getMin() {
        // minStack的栈顶元素即为最小值
        return minStack.peek();
    }
}
public class Test {
}
